/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include<iostream>
#include <string>
#include <unistd.h>
#include<sstream>
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
};
using namespace std;
class Solution {
public:
   // 序列化：将二叉树转换为字符串
    char* Serialize(TreeNode* root) {
        string ret;
        serializeHelper(root, ret);
        return strdup(ret.c_str()); // 返回动态分配的字符串
    }

    // 反序列化：将字符串转换为二叉树
    TreeNode* Deserialize(char* str) {
        if (!str) return nullptr;
        istringstream iss(str);
        return deserializeHelper(iss);
    }

private:
    // 辅助函数：递归序列化
    void serializeHelper(TreeNode* root, string& ret) {
        if (root == nullptr) {
            ret += "# "; // 使用 # 表示空节点
            return;
        }
        ret += to_string(root->val) + " "; // 节点值用空格分隔
        serializeHelper(root->left, ret);
        serializeHelper(root->right, ret);
    }

    // 辅助函数：递归反序列化
    TreeNode* deserializeHelper(istringstream& iss) {
        string val;
        iss >> val; // 从流中读取节点值
        if (val == "#") {
            return nullptr; // 空节点，需要进行标注
        }
        TreeNode* root = new TreeNode(stoi(val)); // 创建节点
        root->left = deserializeHelper(iss); // 递归构造左子树
        root->right = deserializeHelper(iss); // 递归构造右子树
        return root;
    }
};